/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/kth-largest-element-in-an-array
   @Language: C++
   @Datetime: 20-01-08 15:30
   */

// Method 1, min-heap + max-heap, Time O(nlogk), Space O(min(k,n-k)), Time 12ms 82%
class Solution {
	int findKthSmallest(vector<int> &nums, int k){
		priority_queue<int, vector<int>, less<int> > heap;
		for(const auto &num:nums){
			heap.push(num);
			if (heap.size()>k) heap.pop();
		}
		return heap.top();
	}
public:
	int findKthLargest(vector<int>& nums, int k) {
		int n=nums.size();
		if (n<k*2) return findKthSmallest(nums, n-k+1);
		priority_queue<int, vector<int>, greater<int> > heap;
		for(const auto &num:nums){
			heap.push(num);
			if (heap.size()>k) heap.pop();
		}
		return heap.top();
	}
};

// Method 2, partition, Time O(n), Space O(1), Time 8ms 98%
class Solution {
	int partition(vector<int> &nums, int begin, int end){
		int i=begin, j=end-1, key;
		if (i>=j) return i;
		int keyid = begin+rand()%(end-begin);
		swap(nums[i], nums[keyid]);
		for(key=nums[i]; i<j;){
			for(; i<j && nums[j]>=key; --j);
			nums[i] = nums[j];
			for(; i<j && nums[i]<=key; ++i);
			nums[j] = nums[i];
		}
		nums[i] = key;
		return i;
	}
public:
	int findKthLargest(vector<int>& nums, int k) {
		k = nums.size()-k;
		for(int i=0, j=nums.size(), p=-1; p!=k;){
			p = partition(nums, i, j);
			i = p<k ? p+1 : i;
			j = p<k ? j : p;
		}
		return nums[k];
	}
};
